// 弗洛伊德算法求各个顶点之间的最短路径

#include <iostream>
#include <limits>

using namespace std;

// 邻接矩阵
template <typename V, typename E, int M = 10>
struct AMGraph
{
    V vexs[M];
    E arcs[M][M];
    int vexnum;
};

// 弗洛伊德算法求图 G 中各个顶点之间的最短路径
// Floyd(G,P[][],D[][])
// P[i][j] i 到 j 的最短路径上的前驱顶点编号
// D[i][j] i 到 j 的最短路径长度
template <typename V, typename E, int M = 10>
void Floyd(const AMGraph<V, E, M> &G, int P[M][M], E D[M][M])
{
    const E INFINITY = numeric_limits<E>::max();
    // 用邻接矩阵初始化最短路径
    for (int i = 0; i < G.vexnum; i++)
    {
        for (int j = 0; j < G.vexnum; j++)
        {
            D[i][j] = G.arcs[i][j];
            P[i][j] = G.arcs[i][j] != INFINITY ? i : -1;
        } // 计算各顶点之间的最短路径
    }
    for (int k = 0; k < G.vexnum; k++)
    {
        for (int i = 0; i < G.vexnum; i++)
        {
            for (int j = 0; j < G.vexnum; j++)
            {
                //D(k)(i, j)=min{D(k-1)(i,j), D(k-1)(i,k)+D(k-1)(k, j)}。
                if (D[i][k] != INFINITY && D[k][j] != INFINITY && D[i][k] + D[k][j] < D[i][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = P[k][j];
                }
            }
        }
    }
}
int main()
{
    // 建立图
    const int N = 4;
    const int X = numeric_limits<int>::max();
    AMGraph<char, int, N> G{
        {'A', 'B', 'C', 'D'},
        {
            {0, 3, 2, X},
            {X, 0, 4, X},
            {X, X, 0, 5},
            {6, 1, X, 0},
        },
        N,
    };

    // 计算各顶点之间的最短路径
    int P[N][N];
    int D[N][N];

    Floyd(G, P, D);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (D[i][j] != X)
            {
                // 输出 i 到 j 最短路径
                cout << G.vexs[i] << G.vexs[j];
                cout << ' ' << D[i][j] << '(';
                cout << G.vexs[j];
                for (int w = P[i][j];w != i; w = P[i][w])
                {
                    cout << "<-" << G.vexs[w];
                }
                cout << "<-" << G.vexs[i] << ')';
            }
        }
        cout << endl;
    }
    return 0;
}